# Definition for a binary tree node.


# 这道题目给了我们一个二叉树，要我们求出二叉树的倾斜度。题目给了例子真的容易误导人。一开始以为只要求2个children的差值，
# 其实是要求left和
# right各自的总和，包括加上它们自己，left和right两个总和值的差值。利用postorder遍历二叉树，postorder的顺序是左右
# 根。这样的话就可以求出根的sum，左和右都return了以后，加上它自己的值。但是这样的recursivelycall每次返回的都是一个点的sum
# 总值。我们需要求的是差值的总和。所以需要另外设一个res， 每次把差值加入res。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.sum = 0
        self.find(root)
        return self.sum
    def find(self,root):
        if not root:
            return 0
        l = self.find(root.left)
        r = self.find(root.right)
        self.sum += abs(l-r)
        a= self.sum
        # print(l + r +root.val,a)
        return l + r +root.val


m1 = TreeNode(1)
m1.left = TreeNode(2)
# m1.left.left = TreeNode(4)
# m1.left.right = TreeNode(5)
m1.right = TreeNode(3)
# m1.right.left = TreeNode(6)
# m1.right.right = TreeNode(7)
s = Solution()

t = s.findTilt(m1)
print(t)
